/*
 * @lc app=leetcode.cn id=211 lang=typescript
 *
 * [211] 添加与搜索单词 - 数据结构设计
 */

// @lc code=start
class WordDictionary {
  tireRoot: Tire;
  base: number;
  constructor() {
    this.tireRoot = new Tire();
    this.base = 'a'.charCodeAt(0);
  }

  addWord(word: string): void {
    this.tireRoot.insert(word);
  }

  search(word: string): boolean {
    const dfs = (index: number, node: Tire): boolean => {
      if (index === word.length) return node.isEnd;

      const char = word[index];
      if (char === '.') {
        for (const child of node.children) {
          if (child && dfs(index + 1, child)) {
            return true;
          }
        }
      } else {
        const child = node.children[char.charCodeAt(0) - this.base];
        if (child && dfs(index + 1, child)) {
          return true;
        }
      }

      return false;
    };

    return dfs(0, this.tireRoot);
  }
}

class Tire {
  children: Tire[];
  isEnd: boolean;
  base: number;
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
    this.base = 'a'.charCodeAt(0);
  }

  insert(word: string) {
    let node: Tire = this;
    for (let i = 0; i < word.length; i++) {
      const index = word.charCodeAt(i) - this.base;
      if (node.children[index] === null) {
        node.children[index] = new Tire();
      }
      node = node.children[index];
    }
    node.isEnd = true;
  }
}
/**
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */
// @lc code=end
